package com.zzh.tree;

import java.util.Arrays;

public class No96_numTrees {
    public static void main(String[] args) {
        No96Solution solution = new No96Solution();
        int i = solution.numTrees(8);
        System.out.println(i);
    }
}
class No96Solution{
    public int numTrees(int n) {
        int[] f=new int[n+1];
        f[0]=1;//动态规划基准条件
        /*
        * 动态规划的转移方程
        * f(x)=SUM(f(i)*f(x-1-i)) i=0,1,2,3...x-1;
        * */
        int sum;
        for (int i=1;i<=n;i++){
            sum=0;
            for (int j=0;j<i;j++){
                sum+=f[j]*f[i-1-j];
            }
            f[i]=sum;
        }
        return f[n];
    }
}
